package javaCode;

/**
 * Created by lxy_920912 on 2017/1/18.
 */
public class LeetCode322 {
    public int coinChange(int[] coins, int amount) {
        if(amount ==0){
            return  0;
        }
        int []result = new int[amount+1];
        for(int i = 0;i <= amount;i++){
            result[i] = -1;
        }
        for(int i= 0;i < coins.length;i++){
            if(coins[i] <= amount){
                result[coins[i]] = 1;
            }
        }
        int start = 1;
        for(int i= 1;i <= amount;i++){
            if(result[i] == 1){
                start = i;
                break;
            }
        }
        for(;start <= amount;start++){
           if(result[start] != 1){
               for(int j = 0;j < coins.length ;j++){
                   if((coins[j] < start) && result[start-coins[j]] != -1){
                       int num = 1+result[start-coins[j]];
                       if(result[start] ==-1){
                           result[start] = num;
                       }else{
                           result[start] = result[start] < num?result[start]:num;
                       }
                   }
               }
           }
        }
        return result[amount];
    }
}
